package main

import (
	"fmt"
)

// 三分查找
func ThirdSearch(arr []int, data int) int {
	left := 0
	right := len(arr) - 1

	for left <= right {
		//  设置中间的两个分段查找的节点
		mid1 := left + int((right-left)/3)
		mid2 := right - int((right-left)/3)

		fmt.Println(left, mid1, mid2, right)

		dataVal1 := arr[mid1]
		dataVal2 := arr[mid2]

		if data == dataVal1 {
			return mid1
		}

		if data == dataVal2 {
			return mid2
		}

		if dataVal1 > data {
			right = mid1 - 1
		} else if dataVal2 < data {
			left = mid2 + 1
		} else {
			left = mid1 + 1
			right = mid2 - 1
		}
	}

	return -1
}

// 二分查找
func bin_searchG(arr []int, data int) int {
	left := 0
	right := len(arr) - 1

	for left <= right {
		mid1 := left + (right-left)/2

		fmt.Println(left, mid1, right)

		if arr[mid1] > data {

			right = mid1 - 1
		} else if arr[mid1] < data {
			left = mid1 + 1
		} else {
			return mid1
		}
	}

	return -1

}

//
func main() {
	arr := make([]int, 1000, 1000)
	for i := 0; i < 1000; i++ {
		arr[i] = i + 88
	}

	//fmt.Println(arr)
	fmt.Println(ThirdSearch(arr, 777)) // 分七次查找
	fmt.Println("")
	fmt.Println(bin_searchG(arr, 777)) // 分8次查找

}
